/**
*		@file DesignExtractor.cpp
*		@brief DesignExtractor class
*
*		@author Lan Ziquan
*
*		@date 1/25/2012
*/
#include "DesignExtractor.h"

void static DetectUndifinedProcedure();
void static SetProcIdxForStmt();
void static BuildCFG();
void static RebuildTables();
void static ExtractModifiesAndUsesForStmt();
void static ExtractModifiesAndUsesForProc();
void static TransposeTables();
void static CompleteTable();
void static BuildCFGHelper(ProcIdx proc_idx);

// for building cfg usage
struct GNodeHelp{
	GNode* gnode_a;
	GNode* gnode_b;
};

static GNodeHelp* CreateGNodeHelper(GNode* gnode_a, GNode* gnode_b){
	GNodeHelp* new_helper = new GNodeHelp;
	new_helper->gnode_a = gnode_a;
	new_helper->gnode_b = gnode_b;
	return new_helper;
}

void DetectUndifinedProcedure()
{
	ProcIdx first_undefined = ProcTable::GetUndefinedProcIdx();
	if( first_undefined )
	{
		cout << "Detect Undefined Procedure : " << ProcTable::GetProcName(first_undefined) << endl;
		getchar();
		exit(1);
	}
}

void SetProcIdxForStmt()
{
	for( int i = 0; i < ProcTable::GetSize(); i++ )
		for(int j = ProcTable::GetStmtNumStart(i+1); j <= ProcTable::GetStmtNumEnd(i+1); j++ )
			StmtTable::SetProcIdx(j, i+1);
}

void Extract()
{	
	concurrency_counter.resize(10000000);
	int n = 0;
	generate(concurrency_counter.begin(),concurrency_counter.end(),[&](){ return n++;});
	DetectUndifinedProcedure();
	SetProcIdxForStmt();
	BuildCFG();
	RebuildTables();
	ExtractModifiesAndUsesForStmt();
	ExtractModifiesAndUsesForProc();
	TransposeTables();
	CompleteTable();
}

void RebuildTables()
{
	Calls::RebuildCalls();
	Parent::RebuildParent();
	Follows::RebuildFollows();
	Modifies::RebuildModifies();
	Uses::RebuildUses();
	Next::RebuildNext();
	Affects::RebuildAffects();
	BlkTable::RebuildBlkTable();
	NextBip::RebuildNextBip();
	AffectsBip::RebuildAffectsBip();
}

void TransposeTables()
{
	Modifies::TransposeModifies();
	Uses::TransposeUses();
}

void CompleteTable()
{
	Calls::CompleteCalls();
	Parent::CompleteParent();
	Follows::CompleteFollows();
	Modifies::CompleteModifes();
	Uses::CompleteUses();
	Next::CompleteNext();
	NextBip::CompleteNextBip();
}

void ExtractModifiesAndUsesForStmt()
{
	queue<ProcIdx> q_proc_idx = ProcTable::GetProcSequence();

	while( !q_proc_idx.empty() )
	{
		ProcIdx proc_idx_current = q_proc_idx.front();

		TNode* p_tnode_ast_traverser = ProcTable::GetProcASTRoot(proc_idx_current);
		TNode* p_tnode_then_traverser, *p_tnode_else_traverser;
		stack<TNode*> stack_p_tnode;
		stack<TNode*> stack_p_tnode_temp;
		stack_p_tnode.push(p_tnode_ast_traverser);

		while( !stack_p_tnode.empty() )
		{
			p_tnode_ast_traverser = stack_p_tnode.top();

			switch( p_tnode_ast_traverser->type )
			{
			case PROC_TYPE:
				// pop proc, then push all stmt in proc's stmtlst

				stack_p_tnode.pop();
				p_tnode_ast_traverser = p_tnode_ast_traverser->child->child;
				while( p_tnode_ast_traverser != NULL )
				{
					stack_p_tnode_temp.push(p_tnode_ast_traverser);
					p_tnode_ast_traverser = p_tnode_ast_traverser->right_sibling;
				}
				while( !stack_p_tnode_temp.empty() )
				{
					stack_p_tnode.push(stack_p_tnode_temp.top());
					stack_p_tnode_temp.pop();
				}
				break;
			case WHILE_TYPE:
				// push all stmt in while's stmtlst

				p_tnode_ast_traverser = p_tnode_ast_traverser->child->right_sibling->child;
				while( p_tnode_ast_traverser != NULL )
				{
					stack_p_tnode_temp.push(p_tnode_ast_traverser);
					p_tnode_ast_traverser = p_tnode_ast_traverser->right_sibling;
				}
				while( !stack_p_tnode_temp.empty() )
				{
					stack_p_tnode.push(stack_p_tnode_temp.top());
					stack_p_tnode_temp.pop();
				}
				break;

			case IF_TYPE:
				// create two traversers
				p_tnode_then_traverser = p_tnode_ast_traverser->child->right_sibling->child;
				p_tnode_else_traverser = p_tnode_ast_traverser->child->right_sibling->right_sibling->child;

				// push all stmt in if-else's stmtlst
				while( p_tnode_else_traverser != NULL )
				{
					stack_p_tnode_temp.push(p_tnode_else_traverser);
					p_tnode_else_traverser = p_tnode_else_traverser->right_sibling;
				}
				while( !stack_p_tnode_temp.empty() )
				{
					stack_p_tnode.push(stack_p_tnode_temp.top());
					stack_p_tnode_temp.pop();
				}
				// push a copy of if_tnode
				stack_p_tnode.push(p_tnode_ast_traverser);

				// push all stmt in if-then's stmtlst
				while( p_tnode_then_traverser != NULL )
				{
					stack_p_tnode_temp.push(p_tnode_then_traverser);
					p_tnode_then_traverser = p_tnode_then_traverser->right_sibling;
				}
				while( !stack_p_tnode_temp.empty() )
				{
					stack_p_tnode.push(stack_p_tnode_temp.top());
					stack_p_tnode_temp.pop();
				}
				break;
			case CALL_TYPE:
				// construct call_tnode itself
				// then do the same job as assign_tnode
				{
					ProcIdx proc_idx_callee = p_tnode_ast_traverser->value;

					VarSet var_set_proc_modifies (VarTable::GetSize(), false);
					VarSet var_set_proc_uses (VarTable::GetSize(), false);
					for( StmtNum i = ProcTable::GetStmtNumStart(proc_idx_callee);
						i <= ProcTable::GetStmtNumEnd(proc_idx_callee);
						i++ )
					{
						var_set_proc_modifies = LogicOR<VarSet>(var_set_proc_modifies, Modifies::GetModifiesS(i));
						var_set_proc_uses = LogicOR<VarSet>(var_set_proc_uses, Uses::GetUsesS(i));
					}
					Modifies::SetModifiesS(p_tnode_ast_traverser->stmt_num, var_set_proc_modifies);
					Uses::SetUsesS(p_tnode_ast_traverser->stmt_num, var_set_proc_uses);
				}
				// no break
			case ASSIGN_TYPE:
				// pop assign/call
				// if the new top is parent of this assign/call, then recursively set modifies and uses for parent
				// e.g. Parent Relationship: w1->w2->w3->a_this
				//		On Stack: w1->w2->w3->a_this
				//		Loop 1: pop a_this, because Parent(w3,a_this), set modifies for w3, pop w3
				//		Loop 2: because Parent(w2,w3), set modifies for w2, pop w2
				//		Loop 3: because Parent(w1,w2), set modifies for w1, pop w1
				//		Loop 4: empty stack, done

				stack_p_tnode.pop();
				while( !stack_p_tnode.empty() && p_tnode_ast_traverser->parent->parent == stack_p_tnode.top() )
				{
					p_tnode_ast_traverser = stack_p_tnode.top();

					// construct VarSet for modifies
					StmtSet stmt_set_reference = Parent::GetParentRight(p_tnode_ast_traverser->stmt_num);

					VarSet var_set_modifies (Modifies::GetModifiesS(p_tnode_ast_traverser->stmt_num));

					for( unsigned int i = 0; i < stmt_set_reference.size(); i++ )
						if( stmt_set_reference[i] )
							var_set_modifies = LogicOR<VarSet>(var_set_modifies, Modifies::GetModifiesS(i+1));

					// set modifies
					Modifies::SetModifiesS(p_tnode_ast_traverser->stmt_num, var_set_modifies);

					// construct VarSet for uses
					VarSet var_set_uses (Uses::GetUsesS(p_tnode_ast_traverser->stmt_num));
					var_set_uses[p_tnode_ast_traverser->child->value-1] = true; // set uses for while/if condition variable

					for( unsigned int i = 0; i < stmt_set_reference.size(); i++ )
						if( stmt_set_reference[i] )
							var_set_uses = LogicOR<VarSet>(var_set_uses, Uses::GetUsesS(i+1));

					// set uses for while stmt
					Uses::SetUsesS(p_tnode_ast_traverser->stmt_num, var_set_uses);
					stack_p_tnode.pop();
				}
				break;
			default:
				cout << "Invalid TNode type " << p_tnode_ast_traverser->type <<  endl;
				exit(1);
			}
		}
		q_proc_idx.pop();
	}
}

void ExtractModifiesAndUsesForProc()
{
	for( int i = 0; i < ProcTable::GetSize(); i++ )
	{
		VarSet var_set_proc_modifies (VarTable::GetSize(), false);
		VarSet var_set_proc_uses (VarTable::GetSize(), false);
		for( StmtNum j = ProcTable::GetStmtNumStart(i+1);
			j <= ProcTable::GetStmtNumEnd(i+1);
			j++ )
		{
			var_set_proc_modifies = LogicOR<VarSet>(var_set_proc_modifies, Modifies::GetModifiesS(j));
			var_set_proc_uses = LogicOR<VarSet>(var_set_proc_uses, Uses::GetUsesS(j));
		}
		Modifies::SetModifiesP(i+1, var_set_proc_modifies);
		Uses::SetUsesP(i+1, var_set_proc_uses);
	}
}

void BuildCFG(){
	for(int i = 1; i <= ProcTable::GetSize(); i++){
		TNode* current_tnode = ProcTable::GetProcASTRoot(i)->child->child;
		GNode* current_gnode = CreateGNode(current_tnode->type,current_tnode->stmt_num);
		ProcTable::SetProcCFGRoot(i,current_gnode);

		vector<int> traversed(StmtTable::GetSize(),0);
		// 0 has not been done
		// 1 has been done one branch
		// 2 has been done two branch

		vector<GNodeHelp*> gnode_stack;
		vector<int> parent_check;

		while(current_tnode != NULL){
			GNode* new_gnode = NULL;
			if(current_gnode->g_type == IF_TYPE){
				switch(traversed[current_gnode->stmt_num-1]){
				case 0:
					// set one branch has been done
					traversed[current_gnode->stmt_num-1] = 1;

					if(current_tnode->right_sibling != NULL){
						new_gnode = CreateGNode(current_tnode->right_sibling->type,current_tnode->right_sibling->stmt_num);
						gnode_stack.push_back(CreateGNodeHelper(current_gnode,new_gnode));
						parent_check.push_back(gnode_stack.size()-1);
					}
					else gnode_stack.push_back(CreateGNodeHelper(current_gnode,NULL));

					current_tnode = current_tnode->child->right_sibling->child;
					new_gnode = CreateGNode(current_tnode->type,current_tnode->stmt_num);
					current_gnode->next_a = new_gnode;
					current_gnode = new_gnode;
					break;
				case 1:
					// set two branch has been done
					traversed[current_gnode->stmt_num-1] = 2;

					current_tnode = current_tnode->child->right_sibling->right_sibling->child;
					new_gnode = CreateGNode(current_tnode->type,current_tnode->stmt_num);
					current_gnode->next_b = new_gnode;
					current_gnode = new_gnode;
					break;
				default:
					if(gnode_stack.size() == 0) current_tnode = NULL;
					else if(gnode_stack.size() == 1){
						if(parent_check.size() == 0) current_tnode = NULL;
						else{
							current_gnode = gnode_stack[gnode_stack.size()-1]->gnode_b;
							parent_check.pop_back();
							gnode_stack.pop_back();
							current_tnode = StmtTable::GetStmtTNode(current_gnode->stmt_num);
						}
					}
					else{
						if(gnode_stack[gnode_stack.size()-1]->gnode_b != NULL){
							current_gnode = gnode_stack[gnode_stack.size()-1]->gnode_b;
							parent_check.pop_back();
							gnode_stack.pop_back();
						}else{
							gnode_stack.pop_back();
							current_gnode = gnode_stack[gnode_stack.size()-1]->gnode_a;
						}
						current_tnode = StmtTable::GetStmtTNode(current_gnode->stmt_num);
					}
				}
				continue;
			}
			else if(current_gnode->g_type == WHILE_TYPE){
				if(traversed[current_gnode->stmt_num-1] == 0){
					traversed[current_gnode->stmt_num-1] = 1;

					gnode_stack.push_back(CreateGNodeHelper(current_gnode,current_gnode));
					parent_check.push_back(gnode_stack.size()-1);
					current_tnode = current_tnode->child->right_sibling->child;
					new_gnode = CreateGNode(current_tnode->type,current_tnode->stmt_num);
					current_gnode->next_a = new_gnode;
					current_gnode = new_gnode;
					continue;
				}
				else{
					gnode_stack.pop_back();
					parent_check.pop_back();
				}
			}

			if(current_tnode->right_sibling != NULL){
				current_tnode = current_tnode->right_sibling;
				new_gnode = CreateGNode(current_tnode->type,current_tnode->stmt_num);
				if(current_gnode->g_type == WHILE_TYPE){
					current_gnode->next_b = new_gnode;
				}
				else current_gnode->next_a = new_gnode;
				current_gnode = new_gnode;
			}
			else{
				if(parent_check.size() == 0){
					if(gnode_stack.size() == 0) break;
				}
				else{
					if(current_gnode->g_type == WHILE_TYPE){
						current_gnode->next_b = gnode_stack[parent_check[parent_check.size()-1]]->gnode_b;
					}
					else 
						current_gnode->next_a = gnode_stack[parent_check[parent_check.size()-1]]->gnode_b;
				}
				current_gnode = gnode_stack[gnode_stack.size()-1]->gnode_a;
				current_tnode = StmtTable::GetStmtTNode(current_gnode->stmt_num);
			}

		}// end of the big while loop
	}// end of the big for loop
}

